class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        dp[1][1] = 1;
        for(int i = 1; i <= m; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                if(i == 1 && j == 1)
                    continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
};
/*
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> memo(m + 1, vector<int>(n + 1));
        return dfs(m, n, memo);
    }

    int dfs(int sr, int sc, vector<vector<int>>& memo)
    {
        if(sr == 0 || sc == 0)
            return 0;
        if(sr == 1 && sc == 1)
            return 1;

        if(memo[sr][sc] != 0)
            return memo[sr][sc];
        
        memo[sr][sc] = dfs(sr - 1, sc, memo) + dfs(sr, sc - 1, memo);
        return memo[sr][sc];
    }
};
*/